<!DOCTYPE html><html lang="zh-CN"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width, initial-scale=1"><meta name="format-detection" content="telephone=no"><meta name="apple-mobile-web-app-capable" content="yes"><meta name="apple-mobile-web-app-status-bar-style" content="black"><link rel="icon" href="/images/icons/favicon-16x16.png?v=2.6.2" type="image/png" sizes="16x16"><link rel="icon" href="/images/icons/favicon-32x32.png?v=2.6.2" type="image/png" sizes="32x32"><meta name="description" content="复杂度分析       复杂度分析在我看来是数据结构与算法学习入门知识，尤为重要。 为什么复杂度分析重要？ 数据结构与算法的出现本就是为了花更少的时间和空间（储存）来解决问题。复杂度分析就是为解决如何“花更少的时间和空间（储存）”的问题。">
<meta property="og:type" content="article">
<meta property="og:title" content="时间复杂度与空间复杂度">
<meta property="og:url" content="https://kohler19.gitee.io/2022/04/11/complexity/index.html">
<meta property="og:site_name" content="愷龍的网络日志">
<meta property="og:description" content="复杂度分析       复杂度分析在我看来是数据结构与算法学习入门知识，尤为重要。 为什么复杂度分析重要？ 数据结构与算法的出现本就是为了花更少的时间和空间（储存）来解决问题。复杂度分析就是为解决如何“花更少的时间和空间（储存）”的问题。">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://pic.imgdb.cn/item/6253ee49239250f7c5a2b969.jpg">
<meta property="og:image" content="https://s4.ax1x.com/2022/01/03/Tb8ZB4.png">
<meta property="article:published_time" content="2022-04-11T08:50:29.000Z">
<meta property="article:modified_time" content="2022-04-11T12:11:28.568Z">
<meta property="article:author" content="李恺龙">
<meta property="article:tag" content="算法">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://pic.imgdb.cn/item/6253ee49239250f7c5a2b969.jpg"><title>时间复杂度与空间复杂度 | 愷龍的网络日志</title><link ref="canonical" href="https://kohler19.gitee.io/2022/04/11/complexity/"><link rel="dns-prefetch" href="https://cdn.jsdelivr.net"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free@5.12.1/css/all.min.css" type="text/css"><link rel="stylesheet" href="/css/index.css?v=2.6.2"><script>var Stun = window.Stun || {};
var CONFIG = {
  root: '/',
  algolia: undefined,
  assistSearch: undefined,
  fontIcon: {"prompt":{"success":"fas fa-check-circle","info":"fas fa-arrow-circle-right","warning":"fas fa-exclamation-circle","error":"fas fa-times-circle"},"copyBtn":"fas fa-copy"},
  sidebar: {"offsetTop":"20px","tocMaxDepth":6},
  header: {"enable":true,"showOnPost":true,"scrollDownIcon":false},
  postWidget: {"endText":true},
  nightMode: {"enable":true},
  back2top: {"enable":true},
  codeblock: {"style":"default","highlight":"light","wordWrap":false},
  reward: false,
  fancybox: false,
  zoomImage: {"gapAside":"20px"},
  galleryWaterfall: undefined,
  lazyload: false,
  pjax: undefined,
  externalLink: {"icon":{"enable":true,"name":"fas fa-external-link-alt"}},
  shortcuts: undefined,
  prompt: {"copyButton":"复制","copySuccess":"复制成功","copyError":"复制失败"},
  sourcePath: {"js":"js","css":"css","images":"images"},
};

window.CONFIG = CONFIG;</script><meta name="generator" content="Hexo 5.4.0"></head><body><div class="container" id="container"><header class="header" id="header"><div class="header-inner"><nav class="header-nav header-nav--fixed"><div class="header-nav-inner"><div class="header-nav-menubtn"><i class="fas fa-bars"></i></div><div class="header-nav-menu"><div class="header-nav-menu-item"><a class="header-nav-menu-item__link" href="/"><span class="header-nav-menu-item__icon"><i class="fas fa-home"></i></span><span class="header-nav-menu-item__text">首页</span></a></div><div class="header-nav-menu-item"><a class="header-nav-menu-item__link" href="/archives/"><span class="header-nav-menu-item__icon"><i class="fas fa-folder-open"></i></span><span class="header-nav-menu-item__text">归档</span></a></div><div class="header-nav-menu-item"><a class="header-nav-menu-item__link" href="/分类/"><span class="header-nav-menu-item__icon"><i class="fas fa-layer-group"></i></span><span class="header-nav-menu-item__text">分类</span></a></div><div class="header-nav-menu-item"><a class="header-nav-menu-item__link" href="/标签/"><span class="header-nav-menu-item__icon"><i class="fas fa-tags"></i></span><span class="header-nav-menu-item__text">标签</span></a></div><div class="header-nav-menu-item"><a class="header-nav-menu-item__link" href="/categories/Book/"><span class="header-nav-menu-item__icon"><i class="fas fa-book"></i></span><span class="header-nav-menu-item__text">书籍</span></a></div></div><div class="header-nav-search"><span class="header-nav-search__icon"><i class="fas fa-search"></i></span><span class="header-nav-search__text">搜索</span></div><div class="header-nav-mode"><div class="mode"><div class="mode-track"><span class="mode-track-moon"></span><span class="mode-track-sun"></span></div><div class="mode-thumb"></div></div></div></div></nav><div class="header-banner"><div class="header-banner-info"><div class="header-banner-info__title">愷龍的网络日志</div><div class="header-banner-info__subtitle">每天多学一点，以后就少敲一点代码</div></div></div></div></header><main class="main" id="main"><div class="main-inner"><div class="content-wrap" id="content-wrap"><div class="content" id="content"><!-- Just used to judge whether it is an article page--><div id="is-post"></div><div class="post"><header class="post-header"><h1 class="post-title">时间复杂度与空间复杂度</h1><div class="post-meta"><span class="post-meta-item post-meta-item--createtime"><span class="post-meta-item__icon"><i class="far fa-calendar-plus"></i></span><span class="post-meta-item__info">发表于</span><span class="post-meta-item__value">2022-04-11</span></span><span class="post-meta-item post-meta-item--updatetime"><span class="post-meta-item__icon"><i class="far fa-calendar-check"></i></span><span class="post-meta-item__info">更新于</span><span class="post-meta-item__value">2022-04-11</span></span></div></header><div class="post-body">
        <h1 id="复杂度分析"   >
          <a href="#复杂度分析" class="heading-link"><i class="fas fa-link"></i></a><a href="#复杂度分析" class="headerlink" title="复杂度分析"></a>复杂度分析</h1>
      <p>复杂度分析在我看来是数据结构与算法学习入门知识，尤为重要。</p>
<p>为什么复杂度分析重要？</p>
<p>数据结构与算法的出现本就是为了花更少的时间和空间（储存）来解决问题。复杂度分析就是为解决如何“花更少的时间和空间（储存）”的问题。</p>
<span id="more"></span>
<p>现在各种编译工具，代码跑完就能显示用了多少时间，占了多少内存。但是这些数据都是在完成代码编写之后才能得到的，这是事后统计方法。</p>
<p>事后统计法得到的结果会因计算机性能和测试数据规模不同而有较大差异。这并不能体现出代码本身的效率、优劣程度，而且很可能写出的代码本身就不太行。。。</p>
<p>而复杂度分析不依赖软硬件性能、数据规模等就能直接估算算法的效率、优劣，这就是其重要性。</p>

        <h2 id="时间复杂度"   >
          <a href="#时间复杂度" class="heading-link"><i class="fas fa-link"></i></a><a href="#时间复杂度" class="headerlink" title="时间复杂度"></a>时间复杂度</h2>
      <p>时间复杂度即算法的运行时间。</p>
<p>用运行时间去描述算法的效率时，算法的执行总步数越多算法越慢，总步数越少则越快。</p>
<p>假设每一行代码运行时间都为X，则<strong>算法的总运行时间等于运行的总代码行数。</strong></p>
<figure class="highlight c"><div class="table-container"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><code class="hljs C"><span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">sum</span><span class="hljs-params">(n)</span></span>&#123;<br>    sum = <span class="hljs-number">0</span>;<br>    <span class="hljs-keyword">for</span>(i=<span class="hljs-number">0</span>;i&lt;n;i++)&#123;<br>    sum += i;<br>    &#125;<br>    <span class="hljs-keyword">return</span> sum;<br>&#125;<br></code></pre></td></tr></table></div></figure>
<p>在上面代码中，假设运行一行需要 1t，则第二行运行时间为 1t，第四行、第五行执行了n遍，每行运行时间为 nt，则运行总时间就是（1+2n）t</p>
<p>用函数来表示就是 T(n) = (1+2n) t，可以看出T(n)和总步数成正比关系。</p>
<p>用 大O表示法 就是 T(n) = O(f(n))，f(n)为执行总步数。</p>
<p>n可以是1到+∞，当其非常大的时候，一些相对于n来说小的部分就可以忽略了。</p>
<p>拿前面的 1+2n 来说，当n = 100000时，1+2n = 2000001，n持续变大，常数1和系数2对结果影响就很微小了，直接忽略，最终变成了 T(n) = O(n)。</p>
<hr>
<p>下面例子作为练习：   </p>
<figure class="highlight c"><div class="table-container"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><code class="hljs C"><span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">sum</span><span class="hljs-params">(n)</span></span>&#123;<br>    sum=<span class="hljs-number">0</span>;<br>    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;n;i++)&#123;<br>        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=<span class="hljs-number">0</span>;j&lt;n;j++)&#123;<br>            sum +=i+j;<br>        &#125;<br>    &#125;<br>    <span class="hljs-keyword">return</span> sum;<br>&#125;<br></code></pre></td></tr></table></div></figure>
<p>其中有个嵌套for循环，第四行执行1次，第五行、第六行执行n次</p>
<p>第二行需要运行1次，第四行运行n次，第五行、第六行执行n2次，总步数 f(n) = 1 +n +2n^2</p>
<p>当n非常大的时候，对运算结果有影响的是n^2，常数1、n、系数2都可以忽略，则 f(n) = n^2，代码运行时间 T(n) = O(n^2)。   </p>

        <h3 id="常见时间复杂度"   >
          <a href="#常见时间复杂度" class="heading-link"><i class="fas fa-link"></i></a><a href="#常见时间复杂度" class="headerlink" title="常见时间复杂度"></a>常见时间复杂度</h3>
      <center>
<img src="https://pic.imgdb.cn/item/6253ee49239250f7c5a2b969.jpg">
</center>


        <h2 id="最好情况、最坏情况和平均情况时间复杂度"   >
          <a href="#最好情况、最坏情况和平均情况时间复杂度" class="heading-link"><i class="fas fa-link"></i></a><a href="#最好情况、最坏情况和平均情况时间复杂度" class="headerlink" title="最好情况、最坏情况和平均情况时间复杂度"></a>最好情况、最坏情况和平均情况时间复杂度</h2>
      <p>一段代码中，数据的具体情况也会影响运行时间   </p>
<figure class="highlight c"><div class="table-container"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><code class="hljs C"><span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">test</span><span class="hljs-params">(<span class="hljs-built_in">list</span>,num)</span></span>&#123;<br>    <span class="hljs-keyword">int</span> index = <span class="hljs-number">1</span>;<br>    <span class="hljs-keyword">int</span> len = <span class="hljs-built_in">strlen</span>(<span class="hljs-built_in">list</span>);<br>    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">1</span>;i&lt;len;i++)&#123;<br>    <span class="hljs-keyword">if</span>(<span class="hljs-built_in">list</span>[i] == num)&#123;<br>        index = i;<br>        <span class="hljs-keyword">break</span>;<br>        &#125;<br>    &#125;<br>&#125;<br></code></pre></td></tr></table></div></figure>

<p>这段代码是求 变量num 在上列表 list 中的索引</p>
<p>假设输入的 list = [1,2,3,4,5]</p>
<p>当 num = 1 时，自第一次执行时就在list中找到了，后面不再遍历，此时时间复杂度为 O(1)。</p>
<p>当 num = 5 时，全部遍历完才找到，此时时间复杂度为 O(n)。</p>
<p>当 num = 6 时，全部遍历完也没找到，此时时间复杂度也为 O(n)。</p>
<p>这就是数据情况不同，时间复杂度不同。</p>
<p>这样就出现 最好情况、最坏情况时间复杂度。</p>
<p>最好情况时间复杂度就是最理想情况下代码复杂度，对应上面例子最好时间复杂度就是O(1)；</p>
<p>最坏情况时间复杂度就是最不理想情况下代码复杂度，对应上面例子最好时间复杂度就是O(n)；</p>
<p>平均时间复杂度根据加权平均值求得。拿上面例子来说就是 O((3n+1)/4) = O(n)</p>
<p>像最好情况时间复杂度，平均时间复杂度并没有太大参考价值，一般都是拿最坏时间复杂度当时间复杂度，因为不会有比最坏的情况再坏的了，可以说最坏时间复杂度就是一个底线。  </p>

        <h1 id="空间复杂度"   >
          <a href="#空间复杂度" class="heading-link"><i class="fas fa-link"></i></a><a href="#空间复杂度" class="headerlink" title="空间复杂度"></a>空间复杂度</h1>
      <p>空间复杂度反应的是代码运行过程中临时变量占用的内存空间。</p>
<p>代码运行所占空间分为三种：1、代码本身所占空间；2、输入数据所占空间；3、临时变量所占空间</p>
<p>1和2与代码性能无关，所以空间复杂度只考虑运行过程临时占用空间</p>
<p>空间复杂度记作S(n)，表示形式同样为O(f(n))</p>
<figure class="highlight c"><div class="table-container"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><code class="hljs C"><span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">sum</span><span class="hljs-params">(<span class="hljs-built_in">list</span>)</span></span>&#123;<br>    sum = <span class="hljs-number">0</span>;<br>    <span class="hljs-keyword">int</span> len = <span class="hljs-built_in">strlen</span>(<span class="hljs-built_in">list</span>);<br>    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>;i&lt;len;i++)&#123;<br>       sum += <span class="hljs-built_in">list</span>[i];<br>    &#125;<br>    <span class="hljs-keyword">return</span> sum;<br>&#125;<br></code></pre></td></tr></table></div></figure>
<p>该代码求输入列表list中所有元素的和。</p>
<p>其中，输入的list空间不计，sum存储和，i存储元素索引，都是常数，其所占空间与n没有关系，所以该代码空间复杂度S(n) = O(1)   </p>

        <h3 id="常见空间复杂度"   >
          <a href="#常见空间复杂度" class="heading-link"><i class="fas fa-link"></i></a><a href="#常见空间复杂度" class="headerlink" title="常见空间复杂度"></a>常见空间复杂度</h3>
      <figure class="highlight c"><div class="table-container"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><code class="hljs C"><span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">creatList</span><span class="hljs-params">(n)</span></span>&#123;<br>    <span class="hljs-keyword">int</span> <span class="hljs-built_in">list</span>[<span class="hljs-number">100</span>];<br>    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;n;i++)&#123;<br>        <span class="hljs-built_in">list</span>[i]=i;<br>    &#125;<br>    <span class="hljs-keyword">return</span> <span class="hljs-built_in">list</span>[];<br>&#125;<br></code></pre></td></tr></table></div></figure>

<p>其中临时变量有 list和i</p>
<p>list为空列表，所占用空间根据for循环次数增加，最大为n，所以list的空间复杂度为O(n)，i为常数阶，与n无关，则整个代码空间复杂度为O(n)</p>
<p>O(n2):<br>def createList(n):<br>    list1 = []<br>    for i in range(n):<br>        list2 = []<br>        for j in range(n):<br>            list2.append(j)<br>        list1.append(list2)<br>    return list1</p>
<figure class="highlight c"><div class="table-container"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><code class="hljs C"><span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">creatList</span><span class="hljs-params">(n)</span></span>&#123;<br>    <span class="hljs-keyword">int</span> list1[<span class="hljs-number">100</span>];<br>    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;n;i++)&#123;<br>        <span class="hljs-keyword">int</span> list2[<span class="hljs-number">100</span>];<br>        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=<span class="hljs-number">0</span>;j&lt;n;j++)&#123;<br>            list2[j]=j;<br>        &#125;<br>        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> m=<span class="hljs-number">0</span>;m&lt;n;m++)&#123;<br>            list1[m]=list2[m];<br>        &#125;<br><br>    &#125;<br>    <span class="hljs-keyword">return</span> list1[];<br>&#125;<br></code></pre></td></tr></table></div></figure>

<p>这段代码比上面那个多了一层嵌套for循环，(当n小于等于100时)list1的空间占用为n，list2的空间占用为n^2，则整个代码空间复杂度为O(n^2)</p>
<center>如果您有什么问题或建议可以在下方的评论区评论，我会及时回复的。<center>
<center><font color="red">欢迎关注我的公众号，共同学习，共同提升！</font></center>
<center><font color="red">您可以通过公众号向我留言，也可以通过邮箱（lklong@88.com）联系我</font></center>
<center>
    <img src="https://s4.ax1x.com/2022/01/03/Tb8ZB4.png">
</center>


</div><footer class="post-footer"><div class="post-ending ending"><div class="ending__text">------ 本文结束，感谢您的阅读 ------</div></div><div class="post-copyright copyright"><div class="copyright-author"><span class="copyright-author__name">本文作者: </span><span class="copyright-author__value"><a href="https://kohler19.gitee.io">李恺龙</a></span></div><div class="copyright-link"><span class="copyright-link__name">本文链接: </span><span class="copyright-link__value"><a href="https://kohler19.gitee.io/2022/04/11/complexity/">https://kohler19.gitee.io/2022/04/11/complexity/</a></span></div><div class="copyright-notice"><span class="copyright-notice__name">版权声明: </span><span class="copyright-notice__value">本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.en" rel="external nofollow" target="_blank">BY-NC-SA</a> 许可协议。转载请注明出处！</span></div></div><div class="post-tags"><span class="post-tags-item"><span class="post-tags-item__icon"><i class="fas fa-tag"></i></span><a class="post-tags-item__link" href="https://kohler19.gitee.io/tags/%E7%AE%97%E6%B3%95/">算法</a></span></div><nav class="post-paginator paginator"><div class="paginator-prev"><a class="paginator-prev__link" href="/2022/04/13/java-GUI7/"><span class="paginator-prev__icon"><i class="fas fa-angle-left"></i></span><span class="paginator-prev__text">Java-GUI编程之处理位图</span></a></div><div class="paginator-next"><a class="paginator-next__link" href="/2022/04/08/java-GUI6/"><span class="paginator-prev__text">Java-GUI编程之弹球小游戏</span><span class="paginator-next__icon"><i class="fas fa-angle-right"></i></span></a></div></nav></footer></div></div><div class="comments" id="comments"><div id="valine-container"></div></div></div><div class="sidebar-wrap" id="sidebar-wrap"><aside class="sidebar" id="sidebar"><div class="sidebar-nav"><span class="sidebar-nav-toc current">文章目录</span><span class="sidebar-nav-ov">站点概览</span></div><section class="sidebar-toc"><ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#%E5%A4%8D%E6%9D%82%E5%BA%A6%E5%88%86%E6%9E%90"><span class="toc-number">1.</span> <span class="toc-text">
          复杂度分析</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6"><span class="toc-number">1.1.</span> <span class="toc-text">
          时间复杂度</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%B8%B8%E8%A7%81%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6"><span class="toc-number">1.1.1.</span> <span class="toc-text">
          常见时间复杂度</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%9C%80%E5%A5%BD%E6%83%85%E5%86%B5%E3%80%81%E6%9C%80%E5%9D%8F%E6%83%85%E5%86%B5%E5%92%8C%E5%B9%B3%E5%9D%87%E6%83%85%E5%86%B5%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6"><span class="toc-number">1.2.</span> <span class="toc-text">
          最好情况、最坏情况和平均情况时间复杂度</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E7%A9%BA%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6"><span class="toc-number">2.</span> <span class="toc-text">
          空间复杂度</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%B8%B8%E8%A7%81%E7%A9%BA%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6"><span class="toc-number">2.0.1.</span> <span class="toc-text">
          常见空间复杂度</span></a></li></ol></li></ol></li></ol></section><!-- ov = overview--><section class="sidebar-ov hide"><div class="sidebar-ov-author"><div class="sidebar-ov-author__avatar"><img class="sidebar-ov-author__avatar_img" src="https://s4.ax1x.com/2022/01/03/Tb2VW6.png" alt="avatar"></div><p class="sidebar-ov-author__text">格物致知，知行合一</p></div><div class="sidebar-ov-social"><a class="sidebar-ov-social-item" href="https://s4.ax1x.com/2022/01/03/Tb8ZB4.png" target="_blank" rel="noopener" data-popover="微信" data-popover-pos="up"><span class="sidebar-ov-social-item__icon"><i class="fab fa-weixin"></i></span></a><a class="sidebar-ov-social-item" href="mailto:lklong@88.com" target="_blank" rel="noopener" data-popover="social.Email" data-popover-pos="up"><span class="sidebar-ov-social-item__icon">lklong@88.com</span></a></div><div class="sidebar-ov-cc"><a href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.en" target="_blank" rel="noopener" data-popover="知识共享许可协议" data-popover-pos="up"><img src="/images/cc-by-nc-sa.svg"></a></div></section><div class="sidebar-reading"><div class="sidebar-reading-info"><span class="sidebar-reading-info__text">你已阅读了 </span><span class="sidebar-reading-info__num">0</span><span class="sidebar-reading-info__perc">%</span></div><div class="sidebar-reading-line"></div></div></aside></div><div class="clearfix"></div></div></main><footer class="footer" id="footer"><div class="footer-inner"><div><span>Copyright © 2023</span><span class="footer__icon"><i class="fas fa-heart"></i></span><span>愷龍 All Rights Reserved</span></div><div><span>由 <a href="http://hexo.io/" title="Hexo" target="_blank" rel="noopener">Hexo</a> 强力驱动</span><span> v5.4.0</span><span class="footer__devider">|</span><span>主题 - <a href="https://github.com/liuyib/hexo-theme-stun/" title="Stun" target="_blank" rel="noopener">Stun</a></span><span> v2.6.2</span></div></div></footer><div class="loading-bar" id="loading-bar"><div class="loading-bar__progress"></div></div><div class="back2top" id="back2top"><span class="back2top__icon"><i class="fas fa-rocket"></i></span></div></div><div class="search-mask"></div><div class="search-popup"><span class="search-close"></span><div class="search-input"><input placeholder="搜索文章（支持多关键词，请用空格分隔）"></div><div class="search-results"></div></div><script src="https://cdn.jsdelivr.net/npm/jquery@v3.4.1/dist/jquery.min.js"></script><script src="https://cdn.jsdelivr.net/npm/velocity-animate@1.5.2/velocity.min.js"></script><script src="https://cdn.jsdelivr.net/npm/velocity-animate@1.5.2/velocity.ui.min.js"></script><script>function initSearch() {
  var isXML = true;
  var search_path = 'search.xml';

  if (!search_path) {
    search_path = 'search.xml';
  } else if (/json$/i.test(search_path)) {
    isXML = false;
  }

  var path = '/' + search_path;
  $.ajax({
    url: path,
    dataType: isXML ? 'xml' : 'json',
    async: true,
    success: function (res) {
      var datas = isXML ? $('entry', res).map(function () {
        // 将 XML 转为 JSON
        return {
          title: $('title', this).text(),
          content: $('content', this).text(),
          url: $('url', this).text()
        };
      }).get() : res;
      var $input = $('.search-input input');
      var $result = $('.search-results');
      // 搜索对象（标题、内容）的权重，影响显示顺序
      var WEIGHT = { title: 100, content: 1 };
      var searchPost = function () {
        var searchText = $input.val().toLowerCase().trim();
        // 根据空白字符分隔关键字
        var keywords = searchText.split(/[\s]+/);
        // 搜索结果
        var matchPosts = [];

        // 有多个关键字时，将原文字整个保存下来
        if (keywords.length > 1) {
          keywords.push(searchText);
        }
        // 防止未输入字符时搜索
        if (searchText.length > 0) {
          datas.forEach(function (data) {
            var isMatch  = false;
            // 没有标题的文章使用预设的 i18n 变量代替
            var title = (data.title && data.title.trim()) || '[ 文章无标题 ]';
            var titleLower = title && title.toLowerCase();
            // 删除 HTML 标签 和 所有空白字符
            var content = data.content && data.content.replace(/<[^>]+>/g, '');
            var contentLower = content && content.toLowerCase();
            // 删除重复的 /
            var postURL = data.url && decodeURI(data.url).replace(/\/{2,}/g, '/');
            // 标题中匹配到的关键词
            var titleHitSlice = [];
            // 内容中匹配到的关键词
            var contentHitSlice = [];

            keywords.forEach(function (keyword) {
              /**
              * 获取匹配的关键词的索引
              * @param {String} keyword 要匹配的关键字
              * @param {String} text 原文字
              * @param {Boolean} caseSensitive 是否区分大小写
              * @param {Number} weight 匹配对象的权重。权重大的优先显示
              * @return {Array}
              */
              function getIndexByword (word, text, caseSensitive, weight) {
                if (!word || !text) {
                  return [];
                };

                var startIndex = 0; // 每次匹配的开始索引
                var index = -1;     // 匹配到的索引值
                var result = [];    // 匹配结果

                if (!caseSensitive) {
                  word = word.toLowerCase();
                  text = text.toLowerCase();
                }

                while((index = text.indexOf(word, startIndex)) !== -1) {
                  var hasMatch = false;
                  // 索引位置相同的关键词，保留长度较长的
                  titleHitSlice.forEach(function (hit) {
                    if (hit.index === index && hit.word.length < word.length) {
                      hit.word = word;
                      hasMatch = true;
                    }
                  });
                  startIndex = index + word.length;
                  !hasMatch && result.push({ index: index, word: word, weight: weight });
                }
                return result;
              }
              titleHitSlice = titleHitSlice.concat(getIndexByword(keyword, titleLower, false, WEIGHT.title));
              contentHitSlice = contentHitSlice.concat(getIndexByword(keyword, contentLower, false, WEIGHT.content));
            });

            var hitTitle = titleHitSlice.length;
            var hitContent = contentHitSlice.length;

            if (hitTitle > 0 || hitContent > 0) {
              isMatch = true;
            }
            if (isMatch) {
              ;[titleHitSlice, contentHitSlice].forEach(function (hit) {
                // 按照匹配文字的索引的递增顺序排序
                hit.sort(function (left, right) {
                  return left.index - right.index;
                });
              });
              /**
              * 给文本中匹配到的关键词添加标记，从而进行高亮显示
              * @param {String} text 原文本
              * @param {Array} hitSlice 匹配项的索引信息
              * @param {Number} start 开始索引
              * @param {Number} end 结束索引
              * @return {String}
              */
              function highlightKeyword (text, hitSlice, start, end) {
                if (!text || !hitSlice || !hitSlice.length) {
                  return;
                }

                var result = '';
                var startIndex = start;
                var endIndex = end;
                hitSlice.forEach(function (hit) {
                  if (hit.index < startIndex) {
                    return;
                  }

                  var hitWordEnd = hit.index + hit.word.length;
                  result += text.slice(startIndex, hit.index);
                  result += '<b>' + text.slice(hit.index, hitWordEnd) + '</b>';
                  startIndex = hitWordEnd;
                });
                result += text.slice(startIndex, endIndex);
                return result;
              }

              var postData = {};
              // 文章总的搜索权重
              var postWeight = titleHitSlice.length * WEIGHT.title + contentHitSlice.length * WEIGHT.content;
              // 标记匹配关键词后的标题
              var postTitle = highlightKeyword(title, titleHitSlice, 0, title.length) || title;
              // 标记匹配关键词后的内容
              var postContent;
              // 显示内容的长度
              var SHOW_WORD_LENGTH = 200;
              // 命中关键词前的字符显示长度
              var SHOW_WORD_FRONT_LENGTH = 20;
              var SHOW_WORD_END_LENGTH = SHOW_WORD_LENGTH - SHOW_WORD_FRONT_LENGTH;

              // 截取匹配的第一个字符，前后共 200 个字符来显示
              if (contentHitSlice.length > 0) {
                var firstIndex = contentHitSlice[0].index;
                var start = firstIndex > SHOW_WORD_FRONT_LENGTH ? firstIndex - SHOW_WORD_FRONT_LENGTH : 0;
                var end = firstIndex + SHOW_WORD_END_LENGTH;
                postContent = highlightKeyword(content, contentHitSlice, start, end);
              } else { // 未匹配到内容，直接截取前 200 个字符来显示
                postContent = content.slice(0, SHOW_WORD_LENGTH);
              }
              postData.title = postTitle;
              postData.content = postContent;
              postData.url = postURL;
              postData.weight = postWeight;
              matchPosts.push(postData);
            }
          });
        }

        var resultInnerHtml = '';
        if (matchPosts.length) {
          // 按权重递增的顺序排序，使权重大的优先显示
          matchPosts.sort(function (left, right) {
            return right.weight - left.weight;
          });
          resultInnerHtml += '<ul>';
          matchPosts.forEach(function (post) {
            resultInnerHtml += '<li><a class="search-results-title" href="' + post.url + '">';
            resultInnerHtml += post.title;
            resultInnerHtml += '</a><div class="search-results-content">';
            resultInnerHtml += post.content;
            resultInnerHtml += '</div></li>';
          });
          resultInnerHtml += '</ul>';
        } else {
          resultInnerHtml += '<div class="search-results-none"><i class="far fa-meh"></i></div>';
        }
        $result.html(resultInnerHtml);
      };
      $input.on('input', searchPost);
      $input.on('keyup', function (e) {
        if (e.keyCode === Stun.utils.codeToKeyCode('Enter')) {
          searchPost();
        }
      });
    }
  });
}

function closeSearch () {
  $('body').css({ overflow: 'auto' });
  $('.search-popup').css({ display: 'none' });
  $('.search-mask').css({ display: 'none' });
}

window.addEventListener('DOMContentLoaded', function () {
  Stun.utils.pjaxReloadLocalSearch = function () {
    $('.header-nav-search').on('click', function (e) {
      e.stopPropagation();
      $('body').css('overflow', 'hidden');
      $('.search-popup')
        .velocity('stop')
        .velocity('transition.expandIn', {
          duration: 300,
          complete: function () {
            $('.search-popup input').focus();
          }
        });
      $('.search-mask')
        .velocity('stop')
        .velocity('transition.fadeIn', {
          duration: 300
        });

      initSearch();
    });
    $('.search-mask, .search-close').on('click', function () {
      closeSearch();
    });
    $(document).on('keydown', function (e) {
      // Escape <=> 27
      if (e.keyCode === Stun.utils.codeToKeyCode('Escape')) {
        closeSearch();
      }
    });
  };

  Stun.utils.pjaxReloadLocalSearch();
}, false);

function safeOpenUrl(url) {
  var newTab = window.open();
  newTab.opener = null;
  newTab.location = url;
}

function extSearch(engine) {
  var engines = {
    google: 'https://www.google.com/search?q=',
    bing: 'https://cn.bing.com/search?q=',
    baidu: 'https://www.baidu.com/s?ie=UTF-8&wd=',
  };
  var host = window.location.host;
  var query = $('.search-input input').val().toLowerCase().trim();
  var uri = engines[engine] + query + ' site:' + host;

  if (query) {
    safeOpenUrl(uri);
  } else {
    Stun.utils.popAlert('warning', '请输入字符');
  }
}

var assistSearchList = window.CONFIG.assistSearch;

if (Array.isArray(assistSearchList)) {
  assistSearchList.forEach(function (name) {
    document.querySelector('.search-btns-item--' + name).addEventListener('click', function () {
      extSearch(name);
    }, false);
  });
}</script><script src="https://cdn.jsdelivr.net/npm/leancloud-storage@latest/dist/av-min.js"></script><script src="https://cdn.jsdelivr.net/npm/valine@latest/dist/Valine.min.js"></script><script>function loadValine () {
  var GUEST_INFO = ['nick', 'mail', 'link'];
  var guest_info = 'nick,mail,link';

  guest_info = guest_info.split(',').filter(function(item) {
    return GUEST_INFO.indexOf(item) > -1;
  });
  new Valine({
    el: '#valine-container',
    appId: 'lxsmJYFBR3TcsTpKPFWSN0HX-gzGzoHsz',
    appKey: 'lW6taHRzBHFtJeWSSzXXMAxH',
    notify: true,
    verify: true,
    placeholder: 'Just go go',
    avatar: 'mp',
    meta: guest_info,
    pageSize: '10' || 10,
    visitor: false,
    recordIP: false,
    lang: '' || 'zh-cn',
    path: window.location.pathname
  });
}

if (false) {
  loadValine();
} else {
  window.addEventListener('DOMContentLoaded', loadValine, false);
}</script><script src="/js/utils.js?v=2.6.2"></script><script src="/js/stun-boot.js?v=2.6.2"></script><script src="/js/scroll.js?v=2.6.2"></script><script src="/js/header.js?v=2.6.2"></script><script src="/js/sidebar.js?v=2.6.2"></script><script type="application/json" src="/search.xml"></script></body></html>